package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.TreeNode;

public class code106_后序遍历中序遍历构造二叉树 {

    public static void main(String[] args) {
        TreeNode treeNode = new code106_后序遍历中序遍历构造二叉树().buildTree(
                new int[]{9,3,15,20,7},new int[]{9,15,7,20,3}
        );
        System.out.println();
    }

    private int ps =0;

    /**
     * 中序遍历 inorder = [9,3,15,20,7]
     * 后序遍历 postorder = [9,15,7,20,3]
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        ps = postorder.length-1;
        return ans(postorder,inorder,0,inorder.length-1);
    }

    private TreeNode ans(int[] postorder, int[] inorder, int start, int end) {
        if (ps<0||start<0||start>end){
            return null;
        }
        int index = start;
        for (int a=start;a<=end;a++){
            if(postorder[ps] == inorder[a]){
                index = a;
                break;
            }
        }
        TreeNode treeNode = new TreeNode(postorder[ps]);
        ps--;
        treeNode.right = ans(postorder,inorder,index+1,end);
        treeNode.left = ans(postorder,inorder,start,index-1);
        return treeNode;
    }
}
